import org.junit.Test;
import test.ListNode;

/**
 * 2 给定一个链表,返回链表开始第一个入还的第一个节点,如果无环,返回null
 */
public class detectCycle {

    @Test
    public void clibe() {
        ListNode list1 = new ListNode(1,new ListNode(2));
        System.out.println(test1(list1));
    }

    public ListNode test1(ListNode head) {
        if (head == null) return null;
        ListNode slowPtr = head,fastPtr = head;
        boolean loopExists = false;
        while (fastPtr.getNext() != null && fastPtr.getNext().getNext() !=null){
            slowPtr = slowPtr.getNext();
            fastPtr = fastPtr.getNext().getNext();
            if (slowPtr == fastPtr){
                loopExists = true;
                break;
            }
        }
        if (loopExists){
            slowPtr = head;
            while (slowPtr != fastPtr){
                fastPtr = fastPtr.getNext();
                slowPtr = slowPtr.getNext();
            }
            return slowPtr;
        }
        return null;
    }
}
